import java.util.Arrays;

/**
 * Created with IntelliJ IDEA.
 * Description:
 * User:龙宝
 * Date:2023-12-03
 * Time:10:40
 */
public class HeapSort {
    public static void main(String[] args) {
        int[] arr = {1,4,2,6,8,9,7,5,3,0};
        Sort(arr);
        System.out.println(Arrays.toString(arr));
    }

    private static void Sort(int[] arr) {
        //建立一课二叉树（大根堆
        for(int i = arr.length/2-1;i>=0;i--) {
            AdjustHeap(arr,i,arr.length);
        }


        //依次交换
        for(int i = arr.length-1;i>=0;i--) {
            int tmp = arr[i];
            arr[i] = arr[0];
            arr[0] = tmp;
            //整理二叉树
            AdjustHeap(arr,0,i);
        }

    }

    private static void AdjustHeap(int[] arr, int i, int len) {
        while ( 2 * i  + 1 < len) {
            int k = 2 * i +1;
            if(k + 1 < len && arr[k+1] > arr[k]) {
                k++;
            }
            if(arr[k] > arr[i]) {
                int tmp = arr[k];
                arr[k] = arr[i];
                arr[i] = tmp;
                i = k;
            } else {
                break;
            }
        }
    }
}
